package 剑指offer.递归与回溯;

/**
 * 就是给一个字符二维数组，然后给一个字符串，
 * 判断组成字符串的每一个字符在该矩阵里面是否可以构造出一条路径出来
 *
 * 路径要求：可上下左右，但是不可以重复使用进入过的位置
 *
 * 解法：
 * 类似于找迷宫的问题，使用回溯法！！
 *
 * 回溯也是递归
 *
 * 对应于 LeetCode 79
 */
public class 第12题矩阵中的路径 {

    public boolean exist(char[][] board, String word) {
        if (board.length == 0)
            return false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 从i, j点作为起点开始搜索
                if (search(board, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }

    /**
     *
     * @param board 需要搜索的二维数组
     * @param i
     * @param j i、j 是当前搜索的位置
     * @param word 比对用的字符串
     * @param idx 检查 Word 的第 idx 个字符是否等于 i、j 指向的字符
     * @return
     */
    private boolean search(char[][] board, int i, int j, String word, int idx) {
        if (idx >= word.length())
            return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx))
            return false;
        // 将已经搜索过的字母标记一下，防止重复搜索。只要变成另外一个字符，就不会再有重复搜索了。
        board[i][j] ^= 256;
        boolean res = search(board, i - 1, j, word, idx + 1) ||
                search(board, i + 1, j, word, idx + 1) ||
                search(board, i, j - 1, word, idx + 1) ||
                search(board, i, j + 1, word, idx + 1);
        // 再次异或255就能恢复成原来的字母
        board[i][j] ^= 256;
        return res;
    }
}
